/*
 * Copyright (c) 2024. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */
package com.lovely602.algorithm.sort;

/**
 * 简单选择排序
 * <p>每一趟从待排序的数据元素中选出最小的元素，顺序放在待排序的数列最前，直到全部待排序
 * 的数据元素全部排完。
 *
 * <p>选择排序一共有“数组数-1”轮排序，每一轮排序又是一个循环，循环的规则如下：
 *
 * <p>1）先假定当前这轮循环的第一个数是最小数。
 *
 * <p>2）然后和后面每个数进行比较，如果发现有比当前数更小的数，则重新确定最小数，并得到下标。
 *
 * <p>3）当遍历到数组的最后时，就得到本轮最小的数。
 *
 * <p>4）和当前循环的第一个数进行交换。
 *
 * 简单选择排序时间复杂度为 O(n²)。
 *
 * <a href="https://www.dotcpp.com/course/897">课程地址</a>
 *
 * @author lizhixing
 */
public class SelectionSort {


  public static void main(String[] args) {
    int[] arr = new int[] { 19, 26, 8, 35, 41, 77 };
    print(arr);
    selectionSort(arr);
    print(arr);
  }

  public static void selectionSort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) { //每次循环都会找出最小的数
      int minIndex = i; //记录最小数的下标
      int minNum = arr[i]; //记录最小数
      for (int j = i + 1; j < arr.length; j++) { //每次循环都会找出最小的数
        if (arr[j] < minNum) { //如果当前数比最小数小，则更新最小数
          minNum = arr[j]; //更新最小数
          minIndex = j; //更新最小数的下标
        }
      }
      arr[minIndex] = arr[i]; //将最小数放到最前面
      arr[i] = minNum; //将标志位放到最小数原来所在的位置
    }
  }

  private static void print(int[] arr) {
    for (int i : arr) {
      System.out.print(i + "\t");
    }
    System.out.println();
  }

}
